package com.simon.study.algorithm.tree;

import java.util.ArrayDeque;
import java.util.Deque;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;
import org.omg.CORBA.Object;

/**
 * <p>
 *
 * @author simon
 */

public class BPTree<K extends Comparable<K>, V> {

    private Integer degree;
    private BNode<K, V>  root;
    private BLNode<K, V> leafNode;

    private Builder<K, V> builder;


    public BPTree(Integer degree) {
        this.degree   = degree;
        this.builder  = builder(this.degree);
        this.root     = builder.buildBLNode();
        this.leafNode = (BLNode<K, V>) root;
    }


    public void insert(K key){
        this.root = root.insert(key, null);
    }

    public RstInfo<K,V> find(K key){
        return root.find(key);
    }


    public static <K extends Comparable<K>, V> Builder<K,V> builder(int degree){
        return new Builder(degree);
    }

    @NoArgsConstructor
    private static class Builder<K extends Comparable<K>,V>{
        @Setter
        @Getter
        Integer degree;

        public Builder(Integer degree) {
            this.degree = degree;
        }

        public BLNode<K, V> buildBLNode(){
            return new BLNode(degree);
        }
    }


    public static abstract class BNode<K extends Comparable<K>, V>{
        Integer  degree = 7;
        Integer  size;
        K[]      keys;
        BNode    parent;
        BNode[]  children;

        public BNode() {
            this.size   = 0;
            this.keys   = (K[]) new Object[degree];
        }

        public BNode(Integer degree) {
            this.degree = degree;
            this.keys   = (K[]) new Comparable[degree];
            this.size   = 0;
        }

        abstract RstInfo<K, V> find(K key);
        abstract BNode<K, V> insert(K key, V value);
        abstract BNode<K, V> insertNode(BNode<K,V> left, BNode<K,V> right, K oldkey);

        // logical deletion, the data structure need changed
        // mk the value node like: [ int tag; V value; ]
        abstract RstInfo<K, V> delete(K key);

        protected int find(K[] keys, int s, int e, K key){
            int mid =  s + ((e - s) >> 1), ps = s, pe = e;

            while (ps < pe){
                if(keys[mid] == key || keys[mid].compareTo(key) == 0){ return mid; }
                else if(keys[mid].compareTo(key) > 0){ pe = mid; }
                else{ ps = mid+1; }

                mid =  ps + ((pe - ps) >> 1);
            }

            return mid;
        }
    }



    public static class BPNode<K extends Comparable<K>, V> extends BNode<K, V>{
        public BPNode() {
            this.children = new BPNode[degree];
        }

        public BPNode(Integer degree) {
            super(degree);
            this.children = new BNode[degree];
        }

        @Override
        RstInfo<K, V> find(K key) {
            int idx = find(keys, 0, size-1, key);
            return this.children[idx].find(key);
        }

        @Override
        BNode<K, V> insert(K key, V value) {
            int idx = find(keys, 0, size-1, key);
            return this.children[idx].insert(key, value);
        }

        @Override
        BNode<K, V> insertNode(BNode<K, V> left, BNode<K,V> right, K oldkey) {
            // recursive return the root
            if(left   == null){ return parent == null ? this : parent.insertNode(null, null, null); } // nothing to let
            K toldkey = null;
            if(this.size > 0){ toldkey = this.keys[size-1]; }

            if(oldkey == null || size < 1){
                // new node;
                this.keys[size]       =   left.keys[ left.size-1];
                this.children[size++] =   left;
                this.keys[size]       =  right.keys[right.size-1];
                this.children[size++] =  right;
            }else {
                int idx = find(keys, 0, size - 1, oldkey);

                this.keys[idx]       =   left.keys[left.size-1];
                this.children[idx]   =   left;

                if(right == null){ return parent == null ? this : parent.insertNode(null, null, null); }

                if(idx != size-1){
                    // not at end
                    System.arraycopy(keys,     idx+1, keys,     idx+2, size-idx-1);
                    System.arraycopy(children, idx+1, children, idx+2, size-idx-1);
                }
                this.keys[idx+1]       =  right.keys[right.size-1];
                this.children[idx+1]   =  right;
                size++;
            }

            BPNode<K,V> tmp = null;
            if(size == degree){ // todo
                tmp = new BPNode<>(degree);

                if(this.parent == null){ this.parent =  new BPNode(degree);}
                tmp.parent = this.parent;

                int mid   = (degree +1)/2;
                this.size = mid;
                tmp.size  = degree - mid;

                System.arraycopy(this.keys,     mid, tmp.keys,      0, tmp.size);
                System.arraycopy(this.children, mid, tmp.children,  0, tmp.size);
            }

            if(this.parent != null){
                return this.parent.insertNode(this, tmp, toldkey);
            }
            return this;
        }


        @Override
        RstInfo<K, V> delete(K key) {
            int idx = find(keys, 0, size-1, key);
            return this.children[idx].delete(key);
        }
    }

    public static class BLNode<K extends Comparable<K>, V> extends BNode<K,V>{
        V[] values;

        BLNode  left;
        BLNode  right;

        public BLNode() {
            this.values = (V[]) new Object[degree];
        }

        public BLNode(BLNode left) {
            this();
            this.left = left;
        }

        public BLNode(Integer degree) {
            super(degree);
            this.values = (V[]) new Object[degree];
        }

        public BLNode(Integer degree, BLNode left) {
            this(degree);
            this.left = left;
        }

        @Override
        RstInfo<K, V> find(K key) {
            if(size < 1){ return null; }
            int idx = find(keys, 0, size-1, key);

            if(keys[idx] == key || keys[idx].compareTo(key) == 0){ return new RstInfo<>(this, idx); }

            return null;
        }

        @Override
        BNode<K, V> insert(K key, V value) {
            K oldkey = null;
            if( this.size > 0){ oldkey =  this.keys[this.size-1]; }
            if( size < 1 || (keys[size-1] == key || keys[size-1].compareTo(key) < 0)) {
                // add to end
                this.keys[size]     = key;
                this.values[size++] = value;
            }else{
                int idx = find(keys, 0, size-1, key);
                // add in middle
                System.arraycopy(keys,   idx, keys,   idx+1, size-idx);
                System.arraycopy(values, idx, values, idx+1, size-idx);
                size++;
                keys[idx] = key; values[idx] = value;
            }

            BLNode<K,V> tmp = null;
            if(size == degree){ // todo just for reference
                tmp = new BLNode<>(degree, this);

                if( right == null ){ right = tmp; }
                else{
                    BLNode<K,V> ttmp = right;
                    right            = tmp;
                    tmp.right        = ttmp;
                    ttmp.left        = tmp;
                }

                if(this.parent == null){ this.parent =  new BPNode(degree);}
                tmp.parent = this.parent;

                int mid = (degree +1)/2;
                this.size       = mid;
                tmp.size = degree - mid;

                System.arraycopy(this.keys,   mid, tmp.keys,    0, tmp.size);
                System.arraycopy(this.values, mid, tmp.values,  0, tmp.size);
            }

            if(this.parent != null){
                return this.parent.insertNode(this, tmp, oldkey);
            }
            return this;
        }

        @Override
        BNode<K, V> insertNode(BNode<K, V> left, BNode<K, V> right, K oldkey) { return null; }

        @Override
        RstInfo<K, V> delete(K key) {
            return null;
        }
    }

    public void printKeys(){
        if( leafNode == null ){ System.out.println("no data"); }
        BLNode<K,V> leaf = leafNode;
        while (leaf != null){
            for (int i = 0; i < leaf.size; i++) {
                System.out.print( leaf.keys[i] +" " );
            }
            leaf = leaf.right;
        }
        System.out.println();
    }


    public void print(){
        Deque<BNode<K,V>> queue = new ArrayDeque<>();
        int idx = 1, pre = 0;
        queue.addFirst(this.root);

        while (!queue.isEmpty()){
            BNode<K,V> node = queue.pollFirst();
            if(node != null){
                for (int i = 0; i < node.size; i++) {
                    System.out.print(node.keys[i] + " ");
                }

                BNode<K,V>[] children = node.children;
                if(children != null) {
                    for (int i = 0; i < node.size; i++) {
                        queue.addLast(children[i]);
                        pre++;
                    }
                }

                idx--;
                if(idx == 0){ System.out.println(); idx = pre; pre = 0;}
            }
        }
    }

    @NoArgsConstructor
    public static class RstInfo<K extends Comparable<K>,V>{
        BNode<K,V>   rst;
        Integer      idx;

        public RstInfo(BNode<K, V> rst, Integer idx) {
            this.rst = rst;
            this.idx = idx;
        }
    }
}
